package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1371. 每个元音包含偶数次的最长子字符串
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/13 14:03
 */
public class FindTheLongestSubstring {

    public static void main(String[] args) {
        FindTheLongestSubstring test = new FindTheLongestSubstring();
        // 13;
//        String str = "eleetminicoworoep";
        // "8"
//        String str = "amntyyaw";

        // 5
//        String str = "leetcodeisgreat";

        // 6
        String str = "bcbcbc";


        int theLongestSubstring = test.findTheLongestSubstring(str);
        System.out.println(theLongestSubstring);
    }

    public int findTheLongestSubstring(String s) {
        int length = s.length();
        int[][] arr = new int[length][32];
        int[] last = new int[32];
        int max = 0;
        for (int i = 0; i < length; i++) {
            int[] item = arr[i];
            char c = s.charAt(i);
            int n = 5;
            switch (c) {
                case 'a':
                    n = 0;
                    break;
                case 'e':
                    n = 1;
                    break;
                case 'i':
                    n = 2;
                    break;
                case 'o':
                    n = 3;
                    break;
                case 'u':
                    n = 4;
                    break;
            }
            if (n == 5) {
                for (int j = 1; j < 32; j++) {
                    if (last[j] > 0) {
                        item[j] = last[j] + 1;
                    }
                }
                item[0] = last[0] + 1;
            } else {
                n = 1 << n;
                for (int j = 0; j < 32; j++) {
                    if ((j ^ n) == 0) {
                        item[j] = last[0] + 1;
                    } else {
                        if (last[j ^ n] > 0) {
                            item[j] = last[j ^ n] + 1;
                        }
                    }
                }
            }
            max = Math.max(max, item[0]);
            last = item;
        }
        return max;
    }

    /**
     * 官方解法
     * 这道题我做了一下午，看到官方的做法，我顿时感觉自己的思维太蠢了。
     *
     * @param s
     * @return
     */
    public int findTheLongestSubstring2(String s) {
        int n = s.length();
        int[] pos = new int[1 << 5];
        Arrays.fill(pos, -1);
        int ans = 0, status = 0;
        pos[0] = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                status ^= (1 << 0);
            } else if (ch == 'e') {
                status ^= (1 << 1);
            } else if (ch == 'i') {
                status ^= (1 << 2);
            } else if (ch == 'o') {
                status ^= (1 << 3);
            } else if (ch == 'u') {
                status ^= (1 << 4);
            }
            if (pos[status] >= 0) {
                ans = Math.max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        return ans;
    }


}
